/*
https://leetcode.cn/problems/longest-increasing-subsequence/
力扣300.最长递增子序列
*/
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;  //每个数字自己本身就是一个子序列
            for (int j = 0; j < i; ++j) {  
                if (nums[j] < nums[i])   
                    dp[i] = max(dp[i], dp[j] + 1);  //更新数组dp的值
            }
        }

        int res=0;
        for(int i=0;i<n;++i) 
            res=max(res,dp[i]);
        return res;
        /*
        不能返回dp[n-1]，dp[n-1]代表以nums[n-1]结尾的最长递增子序列的长度
        题目要求的是所有子序列中的最长子序列
        所以数组 dp 的最大值才是题目要求的结果。
        例如：
        nums = [2,3,4,5,1]
        dp[n-1] = 1
        */
    }
};

